package slidingWindow;

import java.util.Arrays;
import java.util.HashMap;

public class CheckInclusion {

    /**
     * LeetCode T567 字符串的排列
     *
     * 固定窗口
     * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
     *
     * 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
     *
     * 可以转化为s2的某一个子串中的元素和s1中元素是否相同。
     * @param args
     */
    public static void main(String[] args) {

    }

    public static boolean checkInclusion(String s1, String s2){
        int s1_len = s1.length();
        int s2_len = s2.length();
        if (s2_len < s1_len){
            return false;
        }

        //初始化窗口
        //存放s1的字符种类和数量。初始化的时候即对数组进行了初始化，默认初始化。
        int[] s1_array = new int[26];
        int[] s2_array = new int[26];
        for (int i = 0; i < s1_len; i++){
            ++s1_array[s1.charAt(i)-'a'];
            ++s2_array[s2.charAt(i)-'a'];
        }
        if (Arrays.equals(s1_array, s2_array)){
            return true;
        }
        //窗口进行滑动，同时比对
        for (int i = s1_len; i < s2_len; i++){
            //删除头元素
            --s2_array[s2.charAt(i-s1_len)-'a'];
            //加入尾元素
            ++s2_array[s2.charAt(i)-'a'];
            if (Arrays.equals(s1_array, s2_array)){
                return true;
            }
        }
        return false;
    }
}
